package 算法.leetcode.labuladong.数组和链表;

import java.util.Stack;

/**
 * @author lchenglong
 * @date 2022/6/18
 */
public class 移掉K位数字 {
    class Solution {
        public String removeKdigits(String num, int k) {
            char[] chars = num.toCharArray();
            // 将元素转化为单调栈
            Stack<Character> s = new Stack<>();
            for (char c:num.toCharArray()) {
                while (!s.isEmpty()&&s.peek()>c&&k>0){
                    s.pop();
                    k--;
                }
                if (s.isEmpty()&&c == '0')continue;
                s.push(c);
            }
            // 此时单调栈递增,如果K还大于0,继续出战
            while (!s.isEmpty()&&k>0){
                s.pop();
                --k;
            }
            // 单调栈为空的话,返回0;
            if (s.isEmpty())return "0";
            // 拼接返回值
            StringBuilder sb = new StringBuilder();
            while (!s.isEmpty()){
                sb.append(s.pop());
            }
            // 出栈顺序和字符串是反的
            return sb.reverse().toString();
        }
    }
}
